from typing import List

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # 找右子数组的开头
        h, t = 0, len(nums)
        while h != t:
            s = (h + t) // 2
            if s != nums[s]:
                t = s
            else:
                h = s + 1
        return t

if __name__ == '__main__':
    c = Solution()
    print(c.missingNumber([0,1,2,3,4,5,6,7,9]))